package problems.daily.y2021m7;

import java.util.Arrays;

/**
 * @author habitplus
 * @since 2021-07-14 09:14
 */
public class T20210714N1 {
    // 1818. 绝对差值和
    // 给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。
    // 数组 nums1 和 nums2 的绝对差值和定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的 总和（下标从 0 开始）。
    // 你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。
    // 在替换数组 nums1 中最多一个元素之后，返回最小绝对差值和。
    // 因为答案可能很大，所以需要对 109 + 7 取余 后返回。
    //
    // |x| 定义为：
    //      如果 x >= 0 ，值为 x ，或者
    //      如果 x <= 0 ，值为 -x
    //
    // 提示：
    //      n == nums1.length
    //      n == nums2.length
    //      1 <= n <= 10^5
    //      1 <= nums1[i], nums2[i] <= 10^5
    //
    //链接：https://leetcode-cn.com/problems/minimum-absolute-sum-difference
    public int minAbsoluteSumDiff01(int[] nums1, int[] nums2) {
        // 此方法提交不通过
        int n = nums1.length;

        // 第一遍循环，寻找绝对差值最大的数的下标
        int j = 0, num = 0, t;
        long ans = 0;
        for (int i = 0; i < n; i++) {
            t = Math.abs(nums1[i] - nums2[i]);
            if (num < t) {
                num = t;
                j = i;
            }
            ans += t;
        }

        if (ans == 0) {
            return (int) ans;
        }

        ans -= num;
        // 第二次循环，计算差值总和，并找出替换的数
        for (int k : nums1) {
            t = Math.abs(k - nums2[j]);
            num = Math.min(t, num);
        }
        return (int) ((ans + num) % 1000000007);
    }

    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        // 排序 + 二分查找
        final int MOD = 1000000007;
        int n = nums1.length;
        int[] rec = new int[n];
        System.arraycopy(nums1, 0, rec, 0, n);
        Arrays.sort(rec);
        int sum = 0, maxn = 0;
        for (int i = 0; i < n; i++) {
            int diff = Math.abs(nums1[i] - nums2[i]);
            sum = (sum + diff) % MOD;
            int j = binarySearch(rec, nums2[i]);
            if (j < n) {
                maxn = Math.max(maxn, diff - (rec[j] - nums2[i]));
            }
            if (j > 0) {
                maxn = Math.max(maxn, diff - (nums2[i] - rec[j - 1]));
            }
        }
        return (sum - maxn + MOD) % MOD;
    }

    // 二分查找：类似于搜索插入位置
    // 能找到最靠近 target 的两个数，分别为 rec[low] 和 rec[low-1]
    public int binarySearch(int[] rec, int target) {
        int low = 0, high = rec.length - 1;
        if (rec[high] < target) {
            return high + 1;
        }
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (rec[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}
